﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AlgorithmCenter
{
    public class AlgorithmCenter200910
    {
        private int[,] Dp;
        /// <summary>
        /// dp[i,j]:从前i种物品中选出总重量不超过j的价值最大的物品
        /// dp[i,j]=Max{dp[i,j],dp[i-1,j-k*w[i-1]+k*v[i-1]]}
        /// </summary>
        /// <param name="weight"></param>
        /// <param name="goodsWeight"></param>
        /// <param name="goodsValue"></param>
        /// <returns></returns>
        public int PackageOfComplete(int weight, int[] goodsWeight, int[] goodsValue)
        {
            Dp = new int[goodsWeight.Length+1,weight+1];
            for (int i=1;i<=goodsWeight.Length;i++)
            {
                for (int j=1;j<=weight;j++)
                {
                    for (int k=0;k*goodsWeight[i-1]<=j;k++)
                    {
                        Dp[i, j] = Math.Max(Dp[i,j],Dp[i-1,j-k*goodsWeight[i-1]]+goodsValue[i-1]);
                    }
                }
            }

            return Dp[goodsWeight.Length,weight];
        }
    }
}
